home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / russell / gc.lha / black_list.c < prev    next >
C/C++ Source or Header  |  1993-03-04  |  6KB  |  185 lines
  1. /* 
  2.  * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
  3.  * Copyright (c) 1991, 1992 by Xerox Corporation.  All rights reserved.
  4.  *
  5.  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
  6.  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
  7.  *
  8.  * Permission is hereby granted to copy this garbage collector for any purpose,
  9.  * provided the above notices are retained on all copies.
  10.  */
  11. # include "gc_private.h"
  12.  
  13. /*
  14.  * We maintain several hash tables of hblks that have had false hits.
  15.  * Each contains one bit per hash bucket;  If any page in the bucket
  16.  * has had a false hit, we assume that all of them have.
  17.  * False hits from the stack(s) are much more dangerous than false hits
  18.  * from elsewhere, since the former can pin a large object that spans the
  19.  * block, eventhough it does not start on the dangerous block.
  20.  */
  21.  
  22. /*
  23.  * Externally callable routines are:
  24.  
  25.  * GC_add_to_black_list_normal
  26.  * GC_add_to_black_list_stack
  27.  * GC_promote_black_lists
  28.  * GC_is_black_listed
  29.  *
  30.  * All require that the allocator lock is held.
  31.  */
  32.  
  33. # define LOG_HT_ENTRIES  14    /* Collisions are likely if heap grows    */
  34.                 /* to more than 16K hblks = 64MB.    */
  35.                 /* Each hash table occupies 2K bytes.   */
  36. # define HT_ENTRIES ((word)1 << LOG_HT_ENTRIES)
  37. # define HT_SIZE (HT_ENTRIES >> LOGWL)
  38. typedef word black_list_t[HT_SIZE];
  39.  
  40. # define HASH(addr) (((addr) >> LOG_HBLKSIZE) & (HT_ENTRIES - 1))
  41.  
  42. /* Pointers to individual tables.  We replace one table by another by     */
  43. /* switching these pointers.  GC_black_lists is not used directly.    */
  44. word * GC_new_normal_bl;
  45.         /* Nonstack false references seen at last complete    */
  46.         /* collection.                        */
  47. word * GC_old_normal_bl;
  48.         /* Nonstack false references seen at preceding        */
  49.         /* collection.                        */
  50. word * GC_incomplete_normal_bl;
  51.         /* Nonstack false references seen at current,        */
  52.         /* not yet completed collection.            */
  53. word * GC_new_stack_bl;
  54. word * GC_old_stack_bl;
  55. word * GC_incomplete_stack_bl;
  56.  
  57. # define get_bl_entry_from_index(bl, index) \
  58.         (((bl)[divWORDSZ(index)] >> modWORDSZ(index)) & 1)
  59. # define set_bl_entry_from_index(bl, index) \
  60.         (bl)[divWORDSZ(index)] |= 1 << modWORDSZ(index)
  61. # define clear_bl_entry_from_index(bl, index) \
  62.         (bl)[divWORDSZ(index)] &= ~(1 << modWORDSZ(index))
  63.         
  64. GC_bl_init()
  65. {
  66. # ifndef ALL_INTERIOR_POINTERS
  67.     GC_new_normal_bl = (word *)GC_scratch_alloc((word)(sizeof(black_list_t)));
  68.     GC_old_normal_bl = (word *)GC_scratch_alloc((word)(sizeof (black_list_t)));
  69.     GC_incomplete_normal_bl = (word *)GC_scratch_alloc
  70.                         ((word)(sizeof(black_list_t)));
  71. # endif
  72.     GC_new_stack_bl = (word *)GC_scratch_alloc((word)(sizeof(black_list_t)));
  73.     GC_old_stack_bl = (word *)GC_scratch_alloc((word)(sizeof(black_list_t)));
  74.     GC_incomplete_stack_bl = (word *)GC_scratch_alloc
  75.                         ((word)(sizeof(black_list_t)));
  76. }
  77.         
  78. void GC_clear_bl(doomed)
  79. word *doomed;
  80. {
  81.     bzero((char *)doomed, (int)HT_SIZE*sizeof(word));
  82. }
  83.  
  84. /* Signal the completion of a collection.  Turn the incomplete black    */
  85. /* lists into new black lists, etc.                    */             
  86. void GC_promote_black_lists()
  87. {
  88.     word * very_old_normal_bl = GC_old_normal_bl;
  89.     word * very_old_stack_bl = GC_old_stack_bl;
  90.     
  91.     GC_old_normal_bl = GC_new_normal_bl;
  92.     GC_new_normal_bl = GC_incomplete_normal_bl;
  93.     GC_old_stack_bl = GC_new_stack_bl;
  94.     GC_new_stack_bl = GC_incomplete_stack_bl;
  95. #   ifndef ALL_INTERIOR_POINTERS
  96.       GC_clear_bl(very_old_normal_bl);
  97. #   endif
  98.     GC_clear_bl(very_old_stack_bl);
  99.     GC_incomplete_normal_bl = very_old_normal_bl;
  100.     GC_incomplete_stack_bl = very_old_stack_bl;
  101. }
  102.  
  103. # ifndef ALL_INTERIOR_POINTERS
  104. /* P is not a valid pointer reference, but it falls inside    */
  105. /* the plausible heap bounds.                    */
  106. /* Add it to the normal incomplete black list if appropriate.    */
  107. void GC_add_to_black_list_normal(p)
  108. word p;
  109. {
  110.     if (!(GC_modws_valid_offsets[p & (sizeof(word)-1)])) return;
  111.     {
  112.         register int index = HASH(p);
  113.         
  114.         if (HDR(p) == 0 || get_bl_entry_from_index(GC_new_normal_bl, index)) {
  115. #           ifdef PRINTBLACKLIST
  116.         if (!get_bl_entry_from_index(GC_incomplete_normal_bl, index)) {
  117.               GC_printf1("Black listing (normal) 0x%lx\n",
  118.                        (unsigned long) p);
  119.             }
  120. #           endif
  121.             set_bl_entry_from_index(GC_incomplete_normal_bl, index);
  122.         } /* else this is probably just an interior pointer to an allocated */
  123.           /* object, and isn't worth black listing.                */
  124.     }
  125. }
  126. # endif
  127.  
  128. /* And the same for false pointers from the stack. */
  129. void GC_add_to_black_list_stack(p)
  130. word p;
  131. {
  132.     register int index = HASH(p);
  133.         
  134.     if (HDR(p) == 0 || get_bl_entry_from_index(GC_new_stack_bl, index)) {
  135. #       ifdef PRINTBLACKLIST
  136.         if (!get_bl_entry_from_index(GC_incomplete_stack_bl, index)) {
  137.               GC_printf1("Black listing (stack) 0x%lx\n",
  138.                          (unsigned long)p);
  139.         }
  140. #       endif
  141.     set_bl_entry_from_index(GC_incomplete_stack_bl, index);
  142.     }
  143. }
  144.  
  145. /*
  146.  * Is the block starting at h of size len bytes black listed?   If so,
  147.  * return the address of the next plausible r such that (r, len) might not
  148.  * be black listed.  (R may not actually be in the heap.  We guarantee only
  149.  * that every smaller value of r after h is also black listed.)
  150.  * If (h,len) is not black listed, return 0.
  151.  * Knows about the structure of the black list hash tables.
  152.  */
  153. struct hblk * GC_is_black_listed(h, len)
  154. struct hblk * h;
  155. word len;
  156. {
  157.     register int index = HASH((word)h);
  158.     register word i;
  159.     word nblocks = divHBLKSZ(len);
  160.  
  161. #   ifndef ALL_INTERIOR_POINTERS
  162.       if (get_bl_entry_from_index(GC_new_normal_bl, index)
  163.         && get_bl_entry_from_index(GC_old_normal_bl, index)) {
  164.         return(h+1);
  165.       }
  166. #   endif
  167.     
  168.     for (i = 0; ; ) {
  169.         if (GC_new_stack_bl[divWORDSZ(index)] == 0) {
  170.             /* An easy case */
  171.             i += WORDSZ - modWORDSZ(index);
  172.         } else {
  173.           if (get_bl_entry_from_index(GC_new_stack_bl, index)
  174.             && get_bl_entry_from_index(GC_old_stack_bl, index)) {
  175.             return(h+i+1);
  176.           }
  177.           i++;
  178.         }
  179.         if (i >= nblocks) break;
  180.         index = HASH((word)(h+i));
  181.     }
  182.     return(0);
  183. }
  184.  
  185.